\documentclass[11pt]{ctexart}
\usepackage{graphicx}
\usepackage{ctex}

\title{作业报告}
\author{刘小川  \\ 学号 3210105317}

\begin{document}
\maketitle

在函数 BSTSorting(std::vector<Comparable> \&\_arr, int \_mode = 1) 实现中，我先用if条件语句来判断是否将向量先乱序再排序。关于乱序过程，我使用了函数random\_shuffle来将函数打乱
添加srand((unsigned int)time(0));来保证每次打乱顺序不同。然后将数组里面的每个元素，都插入到新定义的空二叉树里面，因为二叉树的特性，左面元素比右面元素小，因此在插入的过程中，也完成了排序的过程。
因为printTree函数是将二叉树元素从左到右逐步打印，在完成排序后，用printtree将向量按顺序打印出来，这样就完成来排序。
此外，我添加了random.h文件，来生成比较大的随机数组，用于测试该排序算法的运行效率。我添加了vector<int> create\_rand\_int\_number\_include\_a(int a, int b,int num)函数，其内部用到了
 srand((int)time(0));来改变随机种子，函数的形参a,b分别是生成数组元素的上下界，形参num代表着数组的元素个数。这样通过随机的数组生成，来对排序的效率进行测试。\par
随后进行效率测试，通过课堂的学习，我已经了解到，二叉树的最坏效率，是生成的二叉树完全不平衡时，因为这时每次插入都需要进行n次查找才能够找到正确的位置插入，n为插入时树的高度。
当完全不平衡时，算法的复杂度就是O（$ n^{2}$ ）,这是对应的数组应该是一个单调的数组（因为单调的数组生成的二叉树没有任何分支，只向一边延长）。而平均复杂度，通过打乱数据，多次测试来找出。所以，再测试的时候，我们用一个单调的的数组来
测试最坏效率，用一些乱序的随机数组，来查找平均效率。对于较长序列的单调数组，我们可以直接利用打乱后被排好的数组，这样的比较也更加直接。

bash脚本的运行，我的想法是通过多次运行，每一次都能对比一个单调排序和一个乱序的区别，来看最慢效率和平均效率。{\large{\em 在运行测试时，输入的第一个数据为源代码的mode，mode=0时不将向量乱序，
mode=1时将向量打乱顺序后再进行排序。第二个输入数据为flag，我通过设置flag变量，来对最坏和平均效率进行测试。如上所说，当向量本身单调时，排序时间最长。所以当flag为0时，是对随机向量排序
，测试的为平均效率;当flag为1时，生成了一个单调向量，因此测试的是最坏效率。}}\par
下面我用num=10000，即向量长度为10000,分别对排序效率进行测试:\par
mode=0,flag=0此时对平均效率进行测试,测试时间如下\par
{\centering\includegraphics{test1.png}

\centering\includegraphics{test_result1.png}
}
mode=0,flag=1此时对最坏效率进行测试,测试时间如下\par
{\centering\includegraphics{test2.png}

\centering\includegraphics{test_result2.png}
}
\par
可以看出，当对同长度单调向量进行排序时，算法效率更低。


最后，我们检查内存泄漏问题。\par
{\flushleft\includegraphics{check_leaks.png}
}


\end{document}

